// 重建二叉树:
// 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
// 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。


//利用原理,先序遍历的第一个节点就是根。在中序遍历中通过根 区分哪些是左子树的，哪些是右子树的
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    int leftlen = 0, right_len = 0, k = 0;
    if (preorder == NULL || preorderSize == 0) return NULL;
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    node->val = preorder[0];
    while (inorder[k] != preorder[0]) k++;

    //中序遍历
    leftlen = k;    //左子树0~k-1, 大小为k
    right_len = preorderSize-1-k; //右子树k+1~preorderSize-1, 大小为preorderSize-1-k
    
    node->left = buildTree(preorder+1,leftlen,inorder,leftlen); 
    node->right = buildTree(preorder+k+1,right_len,inorder+k+1,right_len);  
    return node;
}